#include "StdAfx.h"
#include "Chain.h"
#include <string>
#include <sstream>
using namespace std;

//--------------------------------------------------------------------------
// PushPermutations: Add permutation to end of list
// Parameters: 
// perm - permutation to add
// Assumes that perm is legal
//--------------------------------------------------------------------------
void Chain::PushPermutation(Permutation* perm)
{
	m_Permutations.push_back(perm);
}

//--------------------------------------------------------------------------
// PopPermutations: Removes last permutation added
//--------------------------------------------------------------------------
Permutation* Chain::PopPermutation()
{
	Permutation* perm = *(m_Permutations.end()-1);
	m_Permutations.pop_back();
	return perm;

}

//--------------------------------------------------------------------------
// IsLegalToAdd : Does perm have a small intersection with all 
//                permutations in chain and can be added
// Returns true if intersection between perm and all perms <= m_MaxIntersection
// and perm is not contained in any of the permutations in the chain
// Parameters:
// perm - Permutation to check
//--------------------------------------------------------------------------
bool Chain::IsLegalToAdd(const Permutation* perm) 
{
	vector<Permutation*>::iterator it;
	for (it = m_Permutations.begin();it < m_Permutations.end(); it++)
	{
		if (perm->GetName() == (*it)->GetName())
		{
			return false;
		}
		int intersectionSize = (*it)->CountIntersection(perm->GetMatrixRows(),perm->GetGroupSize());
		// Illegal permutations:
		// 1. more than max intersection
		// 2. Contain one of the matrices in the chain
		// 3. Are contained in one of the matrices in the chain
		if (intersectionSize > m_MaxIntersection || intersectionSize >= perm->GetGroupSize() || intersectionSize >= (*it)->GetGroupSize())
		{
			return false;
		}
	}
	return true;
}


//--------------------------------------------------------------------------
// Save: Saves chain to xml
// Parameters:
// xml - output xml
// name - chain name
// mimimumLength - minimum length for a chain to be saved
//--------------------------------------------------------------------------
void Chain::Save(CMarkup &xml)
{
	stringstream groupListStream;

	// Save
	xml.AddChildElem(CHAIN_XML);
	xml.IntoElem();
	xml.AddAttrib(CHAIN_NAME_XML,m_Name);
	xml.AddAttrib(CHAIN_LENGTH_XML,m_Permutations.size());
	for (vector<Permutation*>::iterator it = m_Permutations.begin(); it<m_Permutations.end(); it++)
	{
		// Add name to list
		groupListStream << (*it)->GetName() << " ";
		// Save group to XML
		(*it)->SaveToXml(xml);
	}
	string groupList = groupListStream.str();
	// Trim trailing space
	groupList = groupList.substr(0,groupList.length()-1);
	xml.AddAttrib(CHAIN_SUMMARY_XML, groupList);
	xml.OutOfElem();
	
	
}

//--------------------------------------------------------------------------
// Clone: Create copy of chain
// Returns deep copy of chain
//--------------------------------------------------------------------------
Chain *Chain::Clone()
{
	Chain *copy = new Chain(m_MaxIntersection);
	vector<Permutation*>::iterator it;
	for (it= m_Permutations.begin(); it < m_Permutations.end(); it++)
	{
		// Clone each matrix and add to original
		copy->PushPermutation((*it)->Clone());
	}
	return copy;
}	

//--------------------------------------------------------------------------
// RemoveIntersections: Removes intersections between permutations in chain
//						Intersection is removed from smaller group. Erases
//						empty groups.
//--------------------------------------------------------------------------
void Chain::RemoveIntersections()
{
	vector<Permutation*>::iterator it1, it2;
	
	for (size_t it1 = 0; it1 < m_Permutations.size(); it1++)
	{
		// Foreach matrix, go over the next matrices in the chain, check intersections and remove from the smaller one if needed
		for (size_t it2 = it1+1; it2 < m_Permutations.size(); it2++)
		{
			int intersectionSize = m_Permutations[it1]->CountIntersection(m_Permutations[it2]->GetMatrixRows(),m_Permutations[it2]->GetGroupSize());
			
			if (intersectionSize > 0)
			{
				Permutation *permToClean, *otherPerm;
				
				// Permutation 1 is bigger, remove from Permutation 2
				if ((m_Permutations[it1])->GetGroupSize() >= (m_Permutations[it2])->GetGroupSize())
				{
					permToClean = m_Permutations[it2];
					otherPerm = m_Permutations[it1];
				} else
				{
					// Permutation 2 is bigger, remove from Permutation 1
					permToClean = m_Permutations[it1];
					otherPerm = m_Permutations[it2];
				}

				// Update matrix for cleaned matrix
				permToClean->UpdateMatrix(Permutation::GetMatrixWithoutIntersection(permToClean->GetMatrixRows(),permToClean->GetGroupSize(), 
						otherPerm->GetMatrixRows(), otherPerm->GetGroupSize(),intersectionSize), permToClean->GetGroupSize()-intersectionSize);			
			}
		}	
	}

	// Now go over chain and remove all empty permutations
	vector<Permutation*>::iterator it = m_Permutations.begin();
	while (it < m_Permutations.end())
	{
		if ((*it)->GetGroupSize() == 0)
		{
			m_Permutations.erase(it);  // Erase empty permutation
			it = m_Permutations.begin(); // And restart search
		} else
		{
			it++;
		}
	}
}

//--------------------------------------------------------------------------
// Operator== : Compares by permutations
//--------------------------------------------------------------------------
bool Chain::operator== (const Chain &other) const 
{

	if (this == &other)
	{
		return true;
	}

	if (m_Permutations.size() != other.GetLength())
	{
		return false;
	}

	for (size_t i = 0; i < m_Permutations.size(); i++)
	{
		bool found = false;
		vector<Permutation*> otherPerms = other.GetPermutations();
		for (vector<Permutation*>::iterator it = otherPerms.begin(); it < otherPerms.end() && !found; it++)
		{
			if (*(m_Permutations[i]) == *(*it))
			{
				found = true;
			}	
		}
		if (!found)
		{
			return false;
		}
	}

	return true;
}

//--------------------------------------------------------------------------
// Operator!= : Compares by permutations
//-------------------------------------------------------------------------
bool Chain::operator!= (const Chain &other) const
{
	return !(*(this) == other);
}
